package src.stack_queue;

import java.util.*;

public class no20 {
    // 左右括号匹配
    public static void main(String[] args) {

    }

    // java中的栈和队列可用 linkedlist 模拟，因为linkedlist可以获取头尾元素
    public boolean isValid1(String s) {
        //Stack<Character> stack = new Stack<Character>();
        //ArrayDeque<Object> objects = new ArrayDeque<>();

        Deque<Character> deque = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            //当遇到左括号时，就把右括号入栈。之后遇到右括号就直接比较是否和栈顶元素相等，相等就出栈。最终栈空则匹配完成
            if (c == '(') {
                deque.push(')');
            } else if (c == '[') {
                deque.push(']');
            } else if (c == '{') {
                deque.push('}');
            } else if (deque.isEmpty() || deque.peek() != c) {
                return false;
            } else {
                deque.pop();  //以上都不成立时，说明是右括号且匹配成功，则栈顶元素pop
            }
        }
        return deque.isEmpty();

    }

    //用hash表判断是否存在对应的左括号
    public boolean isValid2(String s) {
        if (s.length() % 2 != 0) {
            return false;
        }
        HashMap<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');

        Deque<Object> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                stack.push(map.get(c));  //将扫描到的左括号对应的右括号入栈
            } else if (stack.isEmpty() || !stack.pop().equals(c)) {
                return false;
            }
        }
        return stack.isEmpty();

    }
}
